6. 递归 Recursion

一个函数在函数体内部可以引用自己：

def magic_print(args):
	print(args)
	return magic_print

>>> magic_print(1)(2)(3)(4)(5)
1
2
3
4
5

该函数由于总是返回自身，因此可以无限被引用。

函数可以引用自己是递归的基础。

递归（Recursion） 是指函数直接或间接调用自身的行为。

书写的递归函数是否正确可以通过以下步骤进行基本的测试：

1. 验证最基本的情况（递归返回）是否正确。
2. 对其视为功能抽象，不再考虑其实现细节，只关注其应该完成的行为。
3. 假定函数体内的对更小情况的递归调用是正确的，验证该函数体本身在当前的情况下实现是否正确。

相互递归（Mutual Recursion） 指的则是两个或多个函数相互调用对方的情况，这是一种间接递归。

递归与迭代（Iteration） 之间存在区别与联系。具体而言，迭代是递归的一个特例。在将递归修改为迭代时，重点是关注在迭代过程时需要维护的信息或状态。

将迭代修改为递归则简单很多且总能实现。具体而言，我们需要寻找在每次迭代中保存的参数并将其作为参数传递。

当递归函数内部有不止一次递归调用时，此时的递归图便不再是链状，而是树状，我们称之为树状递归（Tree Recursion）。

树状递归的一个经典例子便是用递归计算斐波那契数列：

def fib(n):
	if n == 0:
		return 0
	elif n == 1:
		return 1
	else:
		return fib(n-1) + fib(n-2)

其递归结构如下：